﻿#define _CRT_SECURE_NO_WARNINGS 1





//https://leetcode.cn/problems/fibonacci-number/description/


//
//【算法原理】
//在搜索的过程中，如果发现特别多完全相同的⼦问题，就可以添加⼀个备忘录，将搜索的结果放在备忘录中。
// 下⼀次在搜索到这个状态时，直接在备忘录⾥⾯拿值。
//

//
//class Solution
//{
//    int f[35];
//public:
//    int dfs(int x)
//    {
//        if (f[x] != -1)
//            return f[x];
//        if (x == 1 || x == 0)
//            return x;
//        f[x] = dfs(x - 1) + dfs(x - 2);
//        return f[x];
//
//    }
//    int fib(int n)
//    {
//        memset(f, -1, sizeof f);
//        return dfs(n);
//    }
//};